#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int upper(vector<int>& arr, int left, int right, int val)
    {
        while (left < right)
        {
            int mid = (left + right) / 2;
            if (val >= arr[mid]) left = mid + 1;
            else right = mid;
        }
        return arr[left];
    }
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        int n1 = arr1.size(), n2 = arr2.size(), intmax = 1e9 + 1;
        sort(arr2.begin(), arr2.end());
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, intmax));
        dp[1][0] = arr1[0], dp[1][1] = min(arr1[0], arr2[0]);
        for (int i = 2; i <= n1; i++)
            for (int j = 0; j <= i && j <= n2; j++)
            {
                if (arr1[i - 1] > dp[i - 1][j]) dp[i][j] = arr1[i - 1];
                int key;
                if (j - 1 >= 0)
                {
                    key = upper(arr2, 0, n2 - 1, dp[i - 1][j - 1]);
                    if (key <= dp[i - 1][j - 1]) key = intmax;
                    dp[i][j] = min(dp[i][j], key);
                }
            }
        for (int j = 0; j <= n2; j++) if (dp[n1][j] != intmax && dp[n1][j] != -1) return j;
        return -1;
    }
};